import java.util.Stack;


/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-06-22
 * Time: 21:16
 */
public class Solution2 {
    //非递归的做法，既可以使用dfs，也可以使用bfs
    boolean isSymmetrical(TreeNode pRoot) {
        //bfs使用队列层次遍历每一层的节点，判断弹出的两个节点是否相等，然后再对称的放入两个节点
        /*if(pRoot==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        //可以使用两个队列，一个专门存放右边的节点，一个专门存放左边的节点，空间复杂度都是O(N)
        //这里使用一个队列，存放一层全部的节点，弹出的时候成对的弹出，插入的时候成对的插入
        queue.offer(pRoot.left);
        queue.offer(pRoot.right);
        while (!queue.isEmpty()){
            TreeNode left=queue.poll();
            TreeNode right=queue.poll();
            if (left == null && right == null) {
                continue;
            }
            if(left==null || right==null){
                return false;
            }
            if(left.val!= right.val){
                return false;
            }
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;*/
        
        //也可以使用dfs,借助栈的特点存放节点
        if(pRoot==null){
            return true;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(pRoot.left);
        stack.push(pRoot.right);
        while (!stack.isEmpty()){
            TreeNode right=stack.pop();
            TreeNode left=stack.pop();
            if(left==null && right==null){
                continue;
            }
            if(left==null || right==null){
                return false;
            }
            if(left.val!=right.val){
                return false;
            }
            stack.push(left.left);
            stack.push(right.right);
            stack.push(left.right);
            stack.push(right.left);
        }
        return true;
        
    }
}
